/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/walls-and-gates
   @Language: C++
   @Datetime: 19-06-13 09:38
   */

class Solution {
	void bfs(vector<vector<int> > &rooms, int r, int c){
		int row=rooms.size(), col=rooms[0].size(), dist=0;
		unordered_set<long> visit;
		queue<pair<long,long> > que;
		for(que.push({r,c}); que.size(); ++dist){
			for(int size=que.size(); size--; que.pop()){
				const auto &p=que.front();
				if(p.first<0 || p.first>=row || p.second<0 || p.second>=col) continue;
				if(rooms[p.first][p.second]==-1) continue;
				if(visit.count((p.first<<32)|p.second)) continue;
				visit.insert((p.first<<32)|p.second);
				if(rooms[p.first][p.second]==0){
					rooms[r][c]=dist;
					return;
				}
				que.push({p.first+1,p.second});
				que.push({p.first-1,p.second});
				que.push({p.first,p.second+1});
				que.push({p.first,p.second-1});
			}
		}
	}
public:
	/**
	 * @param rooms: m x n 2D grid
	 * @return: nothing
	 */
	void wallsAndGates(vector<vector<int> > &rooms) {
		// write your code here
		for(int i=0; i<rooms.size(); ++i)
			for(int j=0; j<rooms[i].size(); ++j)
				if(rooms[i][j]==INT_MAX) bfs(rooms, i, j);
	}
};
